package q2092_findAllPeople;

import CommonClass.UF;

import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class Solution_2 {
    public List<Integer> findAllPeople(int n, int[][] meetings, int firstPerson) {
        UF uf = new UF(n);
        uf.union(0, firstPerson);
        // 按照时间顺序划分区间
        TreeMap<Integer, List<int[]>> map = new TreeMap<>();
        for (int[] meeting : meetings) {
            List<int[]> list = map.getOrDefault(meeting[2], new ArrayList<>());
            list.add(meeting);
            map.put(meeting[2], list);
        }
        // 依次对每个区间进行合并
        for (int key : map.keySet()) {
            // 生成森林同时检查是否有秘密传播，合并树
            for (int[] meeting : map.get(key)) {
                int x = uf.find(meeting[0]);
                int y = uf.find(meeting[1]);
                if (x == 0 || y == 0) {
                    // uf.parent[x] = 0;
                    // uf.parent[y] = 0;
                    uf.union(0, x);
                    uf.union(0, y);
                } else {
                    // uf.union(x, y);
                    uf.parent[x] = uf.parent[y];
                }
            }
            // 第二次删除其他的树（过时视为失效）
            for (int[] meeting : map.get(key)) {
                int x = meeting[0];
                int y = meeting[1];
                if (uf.find(x) != 0) {
                    uf.parent[x] = x;
                    uf.parent[y] = y;
                    // uf.conneted(x, x);

                }
            }
        }
        // 生成结果，树根为0的编号就是知道秘密的人
        List<Integer> res = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (uf.find(i) == 0) {
                res.add(i);
            }
        }
        return res;
    }

}
